// ============================================================================
//
// Graph framework by Aurelien Moreau aurelien.moreau@gmail.com
// Modified by Pierre CHATEL chatelp@gmail.com
// Distributed under LGPL
// Copyright (C) Aurelien Moreau, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.graphFramework.algorithms;

import java.util.Iterator;

import com.thalesgroup.graphFramework.core.Edge;
import com.thalesgroup.graphFramework.core.Graph;
import com.thalesgroup.graphFramework.core.Vertex;

import com.thalesgroup.graphFramework.measure.Measure;

public class BellmannFord {

	static public <S, T> boolean compute(final Graph<S, T> graph,
			final Vertex<S, T> src, final Measure<T> measure) {

		double waux;
		final String W = LeastPathCost.W;
		final String PI = LeastPathCost.PI;

		for(Iterator<Vertex<S,T>> iv=graph.getVertices(); iv.hasNext();) {
			Vertex<S,T> v=iv.next();
			v.setUserFeature(W, 0.);
		}

		for (int i = 0; i < graph.getVerticesSize() - 1; i++) {
			for (Iterator<Edge<S, T>> ie=graph.getEdges(); ie.hasNext();) {
				Edge<S,T> e=ie.next();
				final Double win = ((Double) e.getIn().getUserFeature(W));
				final Double wout = ((Double) e.getOut().getUserFeature(W));
				waux = win + measure.eval(e.getEdge());
				if (waux < wout) {
					e.getOut().setUserFeature(PI, e.getIn());
					e.getOut().setUserFeature(W, waux);
				}
			}
		}

		boolean ok = true;
		for(Iterator<Edge<S,T>> ie=graph.getEdges(); ie.hasNext();) {
			Edge<S,T> e=ie.next();
			final Double win = (Double) e.getIn().getUserFeature(W);
			final Double wout = (Double) e.getOut().getUserFeature(W);
			if ((win + measure.eval(e.getEdge())) < wout) {
				ok = false;
				break;
			}
		}
		return ok;
	}

}
